package com.asia.algorithmcode.binaryTree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @DESCRIPTION: 116、填充每个节点的下一个右侧节点指针
 * @USER: wanfu
 * @DATE: 2025/5/14 星期三 18:19
 */
public class Connect {

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n7 = new Node(7);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6;
        n3.right = n7;

        Node connect = new Connect().connect(n1);

        System.out.println();
    }


    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Node dummy = root;
        while (root.left != null) {
            Node p = root;
            while (p != null) {
                p.left.next = p.right;
                if (p.next != null) {
                    p.right.next = p.next.left;
                }
                p = p.next;
            }
            root = root.left;
        }

        return dummy;
    }

    /**
     * 利用层序遍历的结果，逐个完成同层的指向
     * @param root
     * @return
     */
//    public Node connect(Node root) {
//        if (root == null) {
//            return root;
//        }
//        Deque<Node> list = new LinkedList<>();
//        List<Node> nodes = new ArrayList<>();
//        list.push(root);
//        while (!list.isEmpty()) {
//            int n = list.size();
//            for (int i = 0; i < n; i++) {
//                Node pop = list.pop();
//                nodes.add(pop);
//                if (pop.left != null) {
//                    list.add(pop.left);
//                }
//                if (pop.right != null) {
//                    list.add(pop.right);
//                }
//            }
//            // 将同层的next指针向右侧指
//            for (int i = nodes.size() - 2; i >= 0; i--) {
//                nodes.get(i).next = nodes.get(i + 1);
//            }
//            nodes = new ArrayList<>();
//        }
//        return root;
//    }

}
